package com.sx.sx1.lintcode.day717;

import java.util.*;

public class LC1391 {

    static class Solution {
        /**
         * @param grid:
         * @return: nothing
         */
        public int largestIsland(int[][] grid) {
             //并查集
            int n= grid.length;
            int m = grid[0].length;

            UF  uf = new UF();
            boolean[][] visited = new boolean[n][m];
            List<int[]> pos0 = new ArrayList<>(); //保存0的单元格
            for (int i = 0; i <n ; i++) {
                for (int j = 0; j <m ; j++) {
                    if(grid[i][j] == 1 && !visited[i][j]){

                        dfs(grid,i,j,i*m+j,uf,visited);
                    }

                    if(grid[i][j] ==0){
                        pos0.add(new int[]{i,j});
                    }
                }
            }

            int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};
            int ans =uf.maxsize;
            for (int[] v : pos0) {
                int x = v[0];
                int y = v[1];
                int curans = 1;
                Set<Integer> pids = new HashSet<>();
                for (int[] dir : dirs) {
                    int x1 = x+dir[0];
                    int y1 = y+dir[1];

                    if(x1>=0 && x1<n && y1>=0 && y1<m && grid[x1][y1]==1){
                        int idx = x1*m+y1;

                        int pid = uf.parents.get(idx);
                        if(pids.contains(pid)) continue;
                        pids.add(pid);
                        int size = uf.size.get(pid);
                        curans+= size;
                    }
                }
                ans =Math.max(ans,curans);
            }
            return ans;
        }

        public void dfs(int[][] arr,int i,int j,int pid,UF uf,boolean[][] visited){
            int n= arr.length;
            int m=arr[0].length;
            if(i<0 || i==n || j<0 || j==m || arr[i][j] ==0 || visited[i][j])
                return;

            int curidx = i*m+j;
            uf.union(pid,curidx);
            visited[i][j] =true;
            dfs(arr,i-1,j,pid,uf,visited);
            dfs(arr,i+1,j,pid,uf,visited);
            dfs(arr,i,j-1,pid,uf,visited);
            dfs(arr,i,j+1,pid,uf,visited);
        }

        static class UF{
            public Map<Integer,Integer> parents = new HashMap<>();
            public Map<Integer,Integer> size = new HashMap<>();
            public Map<Integer,Integer> help = new HashMap<>();
            public int sets = 0;
            public int maxsize = 0;
            public int find(int x){
                if (!parents.containsKey(x)) {
                    parents.put(x,x);
                    size.put(x,1);
                    sets++;
                    if(maxsize ==0) maxsize=1;
                }

                int hi=0;
                while (x!=parents.get(x)){
                    help.put(hi++,x);
                    x = parents.get(x);
                }

                for(hi--;hi>=0;hi--){
                    parents.put(help.get(hi),x);
                }

                return x;
            }

            public void union(int a,int b){
                int f1 = find(a);
                int f2 = find(b);

                if(f1!=f2){
                    int s1 = size.get(f1);
                    int s2 = size.get(f2);
                    int s = s1+s2;
                    maxsize = Math.max(maxsize,s);
                    if(s1>=s2){
                        size.put(f1,s);
                        parents.put(f2,f1);
                    }else{
                        size.put(f2,s);
                        parents.put(f1,f2);
                    }
                    sets--;
                }
            }
        }


    }


    public static void main(String[] args) {
        Solution obj = new Solution();
        System.out.println(obj.largestIsland(
                new int[][]
                        {
                                {1,0},
                                {0,1}}));
    }

}

/*
LintCode-Logo
搜索题目、标签、题集
中文
avatar
您有211条未读消息，请及时查看
1391 · 生成更大的陆地
算法
困难
通过率
52%

题目
题解16
笔记
讨论13
排名
记录
描述
在一个只存在 0 和 1 的
𝑛
×
𝑛
n×n 网格中，我们最多将一个 0 改为 1。

之后，最大岛屿的大小是多少？ （一个岛是四个方向上互相连接的一组 1）。

最短时间刷“透”算法面试：《66页算法宝典》.pdf

微信添加【jiuzhangfeifei】备注【66】领取


1 <= grid.length = grid[0] .length <= 50。
0 <= grid [i] [j] <= 1。
样例
样例 1:

输入：[[1,0]，[0,1]]
输出：3

解释：
将0改为1并连接两个1，然后我们得到一个面积= 3的岛。
样例 2:

输入：[[1,1]，[1,0]]
输出：4

解释：
将0更改为1并使岛变大，只有一个面积= 4的岛。
样例 3:

输入：[[1,1]，[1,1]]
输出：4

解释：
不能将任何0更改为1，只有一个面积= 4的岛。
标签
企业
Uber
推荐课程

春招算法高频题冲刺班
精准押题，抱佛脚突击算法面试，最近6个月新题/难题/高频题全覆盖！
20/43
已开启智能提示
发起考试
45 分 00 秒
123456789

控制台
        历史提交

 */